{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode 15 3sum.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "wigHIv5-5rbc"
      },
      "source": [
        "import numpy as np "
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iLMUNvlP_MIt"
      },
      "source": [
        "解法1 时间复杂度O(n^2)， 空间复杂度O(n)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3SKOcvaV_KpI"
      },
      "source": [
        "class Solution(object):\n",
        "    def threeSum(self, nums):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :rtype: List[List[int]]\n",
        "        \"\"\"\n",
        "        \n",
        "        ret = []\n",
        "        \n",
        "        # base case \n",
        "        if len(nums) < 3:\n",
        "            return ret; \n",
        "            \n",
        "        # sort array \n",
        "        # time O(nlogn), space O(1)\n",
        "        nums = sorted(nums)\n",
        "        \n",
        "        # find sum\n",
        "        # time O(n^2), space O(n)\n",
        "        i = 0 \n",
        "        while (i < len(nums)):\n",
        "            j = i + 1\n",
        "            temp = set()\n",
        "            while (j < len(nums)):\n",
        "                if (0 - nums[i] - nums[j] in temp):\n",
        "                    curr = []\n",
        "                    curr.append(nums[i])\n",
        "                    curr.append(nums[j])\n",
        "                    curr.append(0 - nums[i] - nums[j])\n",
        "                    \n",
        "                    ret.append(curr)\n",
        "                    \n",
        "                    while (j < len(nums) - 1 and nums[j] == nums[j+1]):\n",
        "                        j += 1\n",
        "                    \n",
        "                else:\n",
        "                    temp.add(nums[j])\n",
        "                \n",
        "                j += 1 \n",
        "                \n",
        "            while (i < len(nums) - 1 and nums[i] == nums[i+1]):\n",
        "                i += 1 \n",
        "            i += 1 \n",
        "                    \n",
        "        return ret "
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EQhtvPFjES3I",
        "outputId": "10bbd84d-1abb-4bcb-857e-bd6a47750d6d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "s = Solution()\n",
        "nums = [-1,0,1,2,-1,-4]\n",
        "print(s.threeSum(nums))"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[-1, 1, 0], [-1, 2, -1]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8OM8LKhm_mnY"
      },
      "source": [
        "解法2 时间复杂度O(n^2)，空间复杂度O(n)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "u4_140Cr_nsX"
      },
      "source": [
        "class Solution(object):\n",
        "    def threeSum(self, nums):\n",
        "        \n",
        "        # define the return value \n",
        "        ret = []\n",
        "        \n",
        "        # handle the invalid case \n",
        "        if (len(nums) < 3):\n",
        "            return ret; \n",
        "        \n",
        "        nums = sorted(nums)\n",
        "        \n",
        "        # first index  \n",
        "        for i in range(len(nums) - 1):\n",
        "            \n",
        "            if (i > 0 and nums[i] == nums[i-1]):\n",
        "                continue \n",
        "            \n",
        "            # second index \n",
        "            j = i + 1 \n",
        "            # third index \n",
        "            k = len(nums) - 1\n",
        "            while (j < k):\n",
        "                curr = []\n",
        "                if (nums[i] + nums[j] + nums[k] == 0):\n",
        "                    curr.append(nums[i])\n",
        "                    curr.append(nums[j])\n",
        "                    curr.append(nums[k])\n",
        "                    ret.append(curr)\n",
        "                    j += 1 \n",
        "                    k -= 1 \n",
        "                    while (j < k and nums[j-1] == nums[j]):\n",
        "                        j += 1 \n",
        "                    while (j < k and nums[k] == nums[k+1]):\n",
        "                        k -= 1 \n",
        "                elif (nums[i] + nums[j] + nums[k] < 0):\n",
        "                    j += 1 \n",
        "                else:\n",
        "                    k -= 1 \n",
        "                \n",
        "        return ret "
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wM1rBieUEQs4",
        "outputId": "e50a6aba-e37c-4d00-fed1-adfafc968127",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "s = Solution()\n",
        "nums = [-1,0,1,2,-1,-4]\n",
        "print(s.threeSum(nums))"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[-1, -1, 2], [-1, 0, 1]]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}